﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Demo.Framework.Algorithm.Sort
{
    /* Choice of h => 3*x + 1
     * Insertion sort is more efficient of subarray is sorted
     * Shell sort is insertion sort of subarray
     * Advantages
     *  Fast unless array size is huge.
        Tiny, fixed footprint for code (used in embedded systems).
        Hardware sort prototype.
     * */
    class ShellSort<T> : AbstractSort<T>
        where T : IComparable
    {
        public override void Sort(T[] list)
        {
            int count = list.Length;
            int h=3;
            while (h > 1)
            {
                for (int i = 0; i < count; i+=h)
                {
                    for (int j = i; j > 0; j -= h)
                    {
                        if (IsLess(list[j], list[j - h]))
                            Swap(list, j, j - h);
                    }                    
                }
                h--;
            }           
            
        }

        private bool IsLess(T x, T y)
        {
            return x.CompareTo(y) == -1 ? true : false;
        }

        private void Swap(T[] array, int x, int y)
        {
            T temp = array[x];
            array[x] = array[y];
            array[y] = temp;
        }
    }
}
